1786F - Wooden Spoon - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL Mod = 998244353;
void Solve() {
    int n; cin >> n;
    int N = (1 << n);
    vector<LL> fac(N + 1), inv(N + 1), ifac(N + 1);
    fac[0] = fac[1] = inv[1] = ifac[0] = ifac[1] = 1;
    for (int i = 2; i <= N; ++i) {
        fac[i] = fac[i - 1] * i % Mod;
        inv[i] = Mod - Mod / i * inv[Mod % i] % Mod;
        ifac[i] = ifac[i - 1] * inv[i] % Mod;
    }
    function<LL(int, int)> C = [&](int m, int n) {
        if (n < 0 || m < n) return 0ll;
        return fac[m] * ifac[n] % Mod * ifac[m - n] % Mod;
    };
 
    vector<LL> f(N + 1), sum(N + 1);
    f[1] = (N * fac[1 << n - 1]) % Mod;
    for (int i = n - 2; i >= 0; --i) {
        for (int j = 1; j <= N; ++j) sum[j] = (sum[j - 1] + f[j]) % Mod;
        for (int j = 1; j <= N; ++j) {
            f[j] = sum[j - 1] * C(N - j - (1 << i), (1 << i) - 1) % Mod;
            f[j] = f[j] * fac[1 << i] % Mod;
        }
    }
    LL ans = 0;
    for (int i = 1; i <= N; ++i) {
        cout << ans << '\n';
        ans = (ans + f[i]) % Mod;
    }
}
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--) Solve();
    return 0;
}